#ifndef _BTREE_H_
#define _BTREE_H_

#include "Tree.h"
#include "BTreeNode.h"
#include "Exception.h"
#include "LinkQueue.h"
#include "SharedPointer.h"
#include "DualLinkList.h"

namespace MySTL
{

enum BTreeNodePos
{
	ANY,
	LEFT,
	RIGHT
};
enum BTreeTraversal
{
	PreOrder,
	InOrder,
	PostOrder,
	LevelOrder
};

template < typename T >
class BTree : public Tree<T>
{
public:
	bool insert(const T& value, TreeNode<T>* parent);
	virtual bool insert(const T& value, TreeNode<T>* parent, BTreeNodePos pos);
	bool insert(TreeNode<T>* node);
	virtual bool insert(TreeNode<T>* node, BTreeNodePos pos);
	bool remove(TreeNode<T>* node, bool need_to_delete = true);
	BTreeNode<T>* find(const T& value) const;
	BTreeNode<T>* find(TreeNode<T>* node) const;
	BTreeNode<T>* root() const;
	int degree() const;
	int height() const;
	int count() const;
	void clear();

	SharedPointer<DualLinkList<BTreeNode<T>*>> traversal(BTreeTraversal order) const;
	SharedPointer<BTree<T>> clone() const;
	bool operator ==(const BTree<T>& obj) const;
	bool operator !=(const BTree<T>& obj) const;
	SharedPointer<BTree<T>> add(const BTree<T>& obj) const;
	BTreeNode<T>* thread(BTreeTraversal order);

	bool begin();
	bool end();
	bool next();
	BTreeNode<T>* current();

	~BTree();

public:
	static void clear(BTreeNode<T>* root);

protected:
	BTreeNode<T>* find(BTreeNode<T>* root, const T& value) const;
	BTreeNode<T>* find(BTreeNode<T>* root, BTreeNode<T>* node) const;
	int degree(BTreeNode<T>* root) const;
	int height(BTreeNode<T>* root) const;
	int count(BTreeNode<T>* root) const;
	void PreOrderTraversal(BTreeNode<T>* root, DualLinkList<BTreeNode<T>*>& list) const;
	void InOrderTraversal(BTreeNode<T>* root, DualLinkList<BTreeNode<T>*>& list) const;
	void PostOrderTraversal(BTreeNode<T>* root, DualLinkList<BTreeNode<T>*>& list) const;
	void LevelOrderTraversal(BTreeNode<T>* root, DualLinkList<BTreeNode<T>*>& list) const;
	void traversal(BTreeTraversal order, DualLinkList<BTreeNode<T>*>& list) const;
	BTreeNode<T>* clone(BTreeNode<T>* root) const;
	bool equal(BTreeNode<T>* root1, BTreeNode<T>* root2) const;
	BTreeNode<T>* add(BTreeNode<T>* root1, BTreeNode<T>* root2) const;

protected:
	LinkQueue<BTreeNode<T>*> m_foreach_queue;
};

template < typename T >
bool BTree<T>::insert(const T& value, TreeNode<T>* parent)
{
	return insert(value, parent, ANY);
}

template < typename T >
bool BTree<T>::insert(const T& value, TreeNode<T>* parent, BTreeNodePos pos)
{
	BTreeNode<T>* node = BTreeNode<T>::NewNode();
	bool ret = (NULL != node);

	if (ret)
	{
		node->parent = parent;
		node->value = value;

		ret = insert(node, pos);
		if (!ret)
		{
			delete node;
		}
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create BTreeNode in bool BTree<T>::insert(const T& value, TreeNode<T>* parent)");
	}

	return ret;
}

template < typename T >
bool BTree<T>::insert(TreeNode<T>* node)
{
	return insert(node, ANY);
}

template < typename T >
bool BTree<T>::insert(TreeNode<T>* node, BTreeNodePos pos)
{
	BTreeNode<T>* bNode = dynamic_cast<BTreeNode<T>*>(node);
	bool ret = (NULL != bNode) && (pos == LEFT || pos == RIGHT || pos == ANY);

	if (ret)
	{
		if (NULL == root())
		{
			this->m_root = bNode;
			bNode->parent = NULL;
		}
		else
		{
			BTreeNode<T>* parent = find(bNode->parent);
			if ((NULL != parent) && (parent->left != bNode) && (parent->right != bNode))
			{
				if (pos != RIGHT && parent->left == NULL)
				{
					parent->left = bNode;
				}
				else if (pos != LEFT && parent->right == NULL)
				{
					parent->right = bNode;
				}
				else
				{
					ret = false;
				}
			}
			else
			{
				ret = false;
			}
		}
	}

	return ret;
}

template < typename T >
bool BTree<T>::remove(TreeNode<T>* node, bool need_to_delete)
{
	BTreeNode<T>* bNode = find(node);
	bool ret = (NULL != bNode);

	if (ret)
	{
		BTreeNode<T>* parent = dynamic_cast<BTreeNode<T>*>(bNode->parent);
		if (NULL != parent)
		{
			if (parent->left == bNode)
			{
				parent->left = NULL;
			}
			else if (parent->right == bNode)
			{
				parent->right = NULL;
			}
		}
		bNode->parent = NULL;

		if (bNode == root())
		{
			this->m_root = NULL;
		}

		if (need_to_delete)
		{
			clear(bNode);
		}

		m_foreach_queue.clear();
	}

	return ret;
}

template < typename T >
BTreeNode<T>* BTree<T>::find(const T& value) const
{
	return find(root(), value);
}

template < typename T >
BTreeNode<T>* BTree<T>::find(TreeNode<T>* node) const
{
	return find(root(), dynamic_cast<BTreeNode<T>*>(node));
}

template < typename T >
BTreeNode<T>* BTree<T>::root() const
{
	return dynamic_cast<BTreeNode<T>*>(this->m_root);
}

template < typename T >
int BTree<T>::degree() const
{
	return degree(root());
}

template < typename T >
int BTree<T>::height() const
{
	return height(root());
}

template < typename T >
int BTree<T>::count() const
{
	return count(root());
}

template < typename T >
void BTree<T>::clear()
{
	std::cout << root() << std::endl;
	clear(root());
	this->m_root = NULL;
	m_foreach_queue.clear();
}

template < typename T >
SharedPointer<DualLinkList<BTreeNode<T>*>> BTree<T>::traversal(BTreeTraversal order) const
{
	SharedPointer<DualLinkList<BTreeNode<T>*>> ret = new DualLinkList<BTreeNode<T>*>();

	if (!ret.isNull())
	{
		traversal(order, *ret);
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to traversal BTree in SharedPointer<DualLinkList<BTreeNode<T>*>> BTree<T>::traversal(TraversalOrder order) const");
	}

	return ret;
}

template < typename T >
SharedPointer<BTree<T>> BTree<T>::clone() const
{
	SharedPointer<BTree<T>> ret = new BTree<T>();

	if (!ret.isNull())
	{
		ret->m_root = clone(root());
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to clone BTree in SharedPointer<BTree<T>> BTree<T>::clone() const");
	}
	
	return ret;
}

template < typename T >
bool BTree<T>::operator ==(const BTree<T>& obj) const
{
	return equal(root(), obj.root());
}

template < typename T >
bool BTree<T>::operator !=(const BTree<T>& obj) const
{
	return !(*this == obj);
}

template < typename T >
SharedPointer<BTree<T>> BTree<T>::add(const BTree<T>& obj) const
{
	SharedPointer<BTree<T>> ret = new BTree<T>();

	if (!ret.isNull())
	{
		ret->m_root = add(root(), obj.root());
	}
	else
	{
		THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to add BTree in SharedPointer<BTree<T>> BTree<T>::add(const BTree<T>& obj) const");
	}

	return ret;
}

template < typename T >
BTreeNode<T>* BTree<T>::thread(BTreeTraversal order)
{
	BTreeNode<T>* ret = NULL;
	DualLinkList<BTreeNode<T>*> list;

	traversal(order, list);

	if (list.length() > 0 && NULL != list[0])
	{
		BTreeNode<T>* pre = list[0];
		BTreeNode<T>* next = NULL;

		list.remove(0);
		pre->left = NULL;
		ret = pre;

		while (list.length() > 0 && NULL != list[0])
		{
			next = list[0];
			list.remove(0);

			next->left = pre;
			pre->right = next;
			pre = next;
		}

		pre->right = NULL;
	}

	this->m_root = NULL;
	m_foreach_queue.clear();

	return ret;
}

template < typename T >
bool BTree<T>::begin()
{
	bool ret = (NULL != root());

	if (ret)
	{
		m_foreach_queue.clear();
		m_foreach_queue.enqueue(root());
	}

	return ret;
}

template < typename T >
bool BTree<T>::end()
{
	return m_foreach_queue.length() <= 0;
}

template < typename T >
bool BTree<T>::next()
{
	bool ret = !end();

	if (ret)
	{
		BTreeNode<T>* node = m_foreach_queue.dequeue();
		if (NULL != node)
		{
			if (NULL != node->left)
			{
				m_foreach_queue.enqueue(node->left);
			}
			if (NULL != node->right)
			{
				m_foreach_queue.enqueue(node->right);
			}
		}
	}

	return ret;
}

template < typename T >
BTreeNode<T>* BTree<T>::current()
{
	if (!end())
	{
		return m_foreach_queue.top();
	}
	else
	{
		THROW_EXCEPTION(InvalidOperationException, "Invalid operation in BTreeNode<T>* BTree<T>::current()");
	}
}

template < typename T >
BTree<T>::~BTree()
{
	clear();
}

template < typename T >
void BTree<T>::clear(BTreeNode<T>* root)
{
	if (NULL != root)
	{
		clear(root->left);
		clear(root->right);

		BTreeNode<T>* parent = dynamic_cast<BTreeNode<T>*>(root->parent);
		if (NULL != parent)
		{
			if (parent->left == root)
			{
				parent->left = NULL;
			}
			else if (parent->right == root)
			{
				parent->right = NULL;
			}
		}
		root->parent = NULL;

		if (root->need_to_delete())
		{
			delete root;
		}
	}
}

template < typename T >
BTreeNode<T>* BTree<T>::find(BTreeNode<T>* root, const T& value) const
{
	BTreeNode<T>* ret = NULL;

	if (NULL != root)
	{
		if (root->value == value)
		{
			ret = root;
		}
		else
		{
			ret = find(root->left, value);
			if (NULL == ret)
			{
				ret = find(root->right, value);
			}
		}
	}

	return ret;
}

template < typename T >
BTreeNode<T>* BTree<T>::find(BTreeNode<T>* root, BTreeNode<T>* node) const
{
	BTreeNode<T>* ret = NULL;

	if (NULL != root && NULL != node)
	{
		if (root == node)
		{
			ret = root;
		}
		else
		{
			ret = find(root->left, node);
			if (NULL == ret)
			{
				ret = find(root->right, node);
			}
		}
	}

	return ret;
}

template < typename T >
int BTree<T>::degree(BTreeNode<T>* root) const
{
	int ret = 0;

	if (root)
	{
		if (NULL != root->left)
		{
			++ret;
		}
		if (NULL != root->right)
		{
			++ret;
		}
		if (ret == 1)
		{
			int d = root->left ? degree(root->left) : degree(root->right);
			if (d > ret)
			{
				ret = 2;
			}
		}
	}

	return ret;
}

template < typename T >
int BTree<T>::height(BTreeNode<T>* root) const
{
	int ret = 0;

	if (NULL != root)
	{
		int left = height(root->left);
		int right = height(root->right);

		ret = (left > right ? left : right) + 1;
	}

	return ret;
}

template < typename T >
int BTree<T>::count(BTreeNode<T>* root) const
{
	int ret = 0;

	if (root)
	{
		ret = count(root->left) + count(root->right) + 1;
	}

	return ret;
}

template < typename T >
void BTree<T>::PreOrderTraversal(BTreeNode<T>* root, DualLinkList<BTreeNode<T>*>& list) const
{
	if (NULL != root)
	{
		list.insert(root);
		PreOrderTraversal(root->left, list);
		PreOrderTraversal(root->right, list);
	}
}

template < typename T >
void BTree<T>::InOrderTraversal(BTreeNode<T>* root, DualLinkList<BTreeNode<T>*>& list) const
{
	if (NULL != root)
	{
		InOrderTraversal(root->left, list);
		list.insert(root);
		InOrderTraversal(root->right, list);
	}
}

template < typename T >
void BTree<T>::PostOrderTraversal(BTreeNode<T>* root, DualLinkList<BTreeNode<T>*>& list) const
{
	if (NULL != root)
	{
		PostOrderTraversal(root->left, list);
		PostOrderTraversal(root->right, list);
		list.insert(root);
	}
}

template < typename T >
void BTree<T>::LevelOrderTraversal(BTreeNode<T>* root, DualLinkList<BTreeNode<T>*>& list) const
{
	if (NULL != root)
	{
		LinkQueue<BTreeNode<T>*> tmp_queue;
		tmp_queue.enqueue(root);

		while (tmp_queue.length() > 0)
		{
			BTreeNode<T>* node = tmp_queue.dequeue();

			if (NULL != node)
			{
				list.insert(node);

				if (NULL != node->left)
					tmp_queue.enqueue(node->left);
				if (NULL != node->right)
					tmp_queue.enqueue(node->right);
			}
		}
	}
}

template < typename T >
void BTree<T>::traversal(BTreeTraversal order, DualLinkList<BTreeNode<T>*>& list) const
{
	switch (order)
	{
	case PreOrder:
		PreOrderTraversal(root(), list);
		break;
	case InOrder:
		InOrderTraversal(root(), list);
		break;
	case PostOrder:
		PostOrderTraversal(root(), list);
		break;
	case LevelOrder:
		LevelOrderTraversal(root(), list);
		break;
	default:
		THROW_EXCEPTION(ParameterErrorException, "Parameter order error in BTreeNode<T>* BTree<T>::thread(BTreeTraversal order)");
		break;
	}
}

template < typename T >
BTreeNode<T>* BTree<T>::clone(BTreeNode<T>* root) const
{
	BTreeNode<T>* ret = NULL;

	if (NULL != root)
	{
		ret = BTreeNode<T>::NewNode();
		
		if (NULL != ret)
		{
			ret->value = root->value;
			ret->parent = NULL;
			ret->left = clone(root->left);
			ret->right = clone(root->right);

			if (NULL != ret->left)
				ret->left->parent = ret;
			if (NULL != ret->right)
				ret->right->parent = ret;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to clone BTree in BTreeNode<T>* BTree<T>::clone(BTreeNode<T>* root) const");
		}
	}

	return ret;
}

template < typename T >
bool BTree<T>::equal(BTreeNode<T>* root1, BTreeNode<T>* root2) const
{
	bool ret = (root1 == root2);

	if (root1 && root2)
	{
		if (root1->value == root2->value)
		{
			ret = equal(root1->left, root2->left) && equal(root1->right, root2->right);
		}
	}

	return ret;
}

template < typename T >
BTreeNode<T>* BTree<T>::add(BTreeNode<T>* root1, BTreeNode<T>* root2) const
{
	BTreeNode<T>* ret = NULL;

	if (root1 && root2)
	{
		ret = BTreeNode<T>::NewNode();

		if (NULL != ret)
		{
			ret->value = root1->value + root2->value;
			ret->parent = NULL;
			ret->left = add(root1->left, root2->left);
			ret->right = add(root1->right, root2->right);

			if (NULL != ret->left)
				ret->left->parent = ret;
			if (NULL != ret->right)
				ret->right->parent = ret;
		}
		else
		{
			THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to add BTree in BTreeNode<T>* BTree<T>::add(BTreeNode<T>* root1, BTreeNode<T>* root2) const");
		}
	}
	else if (root1 && !root2)
	{
		ret = clone(root1);
	}
	else if (!root1 && root2)
	{
		ret = clone(root2);
	}

	return ret;
}

}

#endif